PittsburghV1, Main, Exploration, bibRecord, 000A70

Trinary-projection trees for approximate nearest neighbor search.

Identifieur interne : 000A70 ( Main/Exploration ); précédent : 000A69; suivant : 000A71

Trinary-projection trees for approximate nearest neighbor search.

Auteurs : Jingdong Wang [République populaire de Chine] ; Naiyan Wang [Hong Kong] ; You Jia [États-Unis] ; Jian Li [République populaire de Chine] ; Gang Zeng [République populaire de Chine] ; Hongbin Zha [République populaire de Chine] ; Xian-Sheng Hua

Source :

IEEE transactions on pattern analysis and machine intelligence [ 1939-3539 ] ; 2014.

RBID : pubmed:24356357

Descripteurs français

English descriptors

Abstract

We address the problem of approximate nearest neighbor (ANN) search for visual descriptor indexing. Most spatial partition trees, such as KD trees, VP trees, and so on, follow the hierarchical binary space partitioning framework. The key effort is to design different partition functions (hyperplane or hypersphere) to divide the points so that 1) the data points can be well grouped to support effective NN candidate location and 2) the partition functions can be quickly evaluated to support efficient NN candidate location. We design a trinary-projection direction-based partition function. The trinary-projection direction is defined as a combination of a few coordinate axes with the weights being 1 or -1. We pursue the projection direction using the widely adopted maximum variance criterion to guarantee good space partitioning and find fewer coordinate axes to guarantee efficient partition function evaluation. We present a coordinate-wise enumeration algorithm to find the principal trinary-projection direction. In addition, we provide an extension using multiple randomized trees for improved performance. We justify our approach on large-scale local patch indexing and similar image search.

DOI: 10.1109/TPAMI.2013.125
PubMed: 24356357

Affiliations:

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Trinary-projection trees for approximate nearest neighbor search.</title>
<author><name sortKey="Wang, Jingdong" sort="Wang, Jingdong" uniqKey="Wang J" first="Jingdong" last="Wang">Jingdong Wang</name>
<affiliation wicri:level="3"><nlm:affiliation>Microsoft Research Aisa, Beijing.</nlm:affiliation>
<country>République populaire de Chine</country>
<placeName><settlement type="city">Pékin</settlement>
</placeName>
<wicri:orgArea>Microsoft Research Aisa</wicri:orgArea>
</affiliation>
</author>
<author><name sortKey="Wang, Naiyan" sort="Wang, Naiyan" uniqKey="Wang N" first="Naiyan" last="Wang">Naiyan Wang</name>
<affiliation wicri:level="1"><nlm:affiliation>The Hong Kong University of Science and Technology, Hong Kong.</nlm:affiliation>
<country xml:lang="fr">Hong Kong</country>
<wicri:regionArea>The Hong Kong University of Science and Technology</wicri:regionArea>
</affiliation>
</author>
<author><name sortKey="Jia, You" sort="Jia, You" uniqKey="Jia Y" first="You" last="Jia">You Jia</name>
<affiliation wicri:level="3"><nlm:affiliation>Carnegie Mellon University, Pittsburgh.</nlm:affiliation>
<country>États-Unis</country>
<placeName><settlement type="city">Pittsburgh</settlement>
<region type="state">Pennsylvanie</region>
</placeName>
<wicri:orgArea>Carnegie Mellon University</wicri:orgArea>
</affiliation>
</author>
<author><name sortKey="Li, Jian" sort="Li, Jian" uniqKey="Li J" first="Jian" last="Li">Jian Li</name>
<affiliation wicri:level="3"><nlm:affiliation>Tsinghua University, Beijing.</nlm:affiliation>
<country>République populaire de Chine</country>
<placeName><settlement type="city">Pékin</settlement>
</placeName>
<wicri:orgArea>Tsinghua University</wicri:orgArea>
</affiliation>
</author>
<author><name sortKey="Zeng, Gang" sort="Zeng, Gang" uniqKey="Zeng G" first="Gang" last="Zeng">Gang Zeng</name>
<affiliation wicri:level="3"><nlm:affiliation>Peking University, Beijing.</nlm:affiliation>
<country>République populaire de Chine</country>
<placeName><settlement type="city">Pékin</settlement>
</placeName>
<wicri:orgArea>Peking University</wicri:orgArea>
</affiliation>
</author>
<author><name sortKey="Zha, Hongbin" sort="Zha, Hongbin" uniqKey="Zha H" first="Hongbin" last="Zha">Hongbin Zha</name>
<affiliation wicri:level="3"><nlm:affiliation>Peking University, Beijing.</nlm:affiliation>
<country>République populaire de Chine</country>
<placeName><settlement type="city">Pékin</settlement>
</placeName>
<wicri:orgArea>Peking University</wicri:orgArea>
</affiliation>
</author>
<author><name sortKey="Hua, Xian Sheng" sort="Hua, Xian Sheng" uniqKey="Hua X" first="Xian-Sheng" last="Hua">Xian-Sheng Hua</name>
<affiliation><nlm:affiliation>Microsoft Corporation, Bellevue.</nlm:affiliation>
<wicri:noCountry code="subField">Bellevue</wicri:noCountry>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PubMed</idno>
<date when="2014">2014</date>
<idno type="RBID">pubmed:24356357</idno>
<idno type="pmid">24356357</idno>
<idno type="doi">10.1109/TPAMI.2013.125</idno>
<idno type="wicri:Area/PubMed/Corpus">003D13</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">003D13</idno>
<idno type="wicri:Area/PubMed/Curation">003C86</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">003C86</idno>
<idno type="wicri:Area/PubMed/Checkpoint">003C86</idno>
<idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">003C86</idno>
<idno type="wicri:Area/Ncbi/Merge">000927</idno>
<idno type="wicri:Area/Ncbi/Curation">000927</idno>
<idno type="wicri:Area/Ncbi/Checkpoint">000927</idno>
<idno type="wicri:Area/Main/Merge">000A78</idno>
<idno type="wicri:Area/Main/Curation">000A70</idno>
<idno type="wicri:Area/Main/Exploration">000A70</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Trinary-projection trees for approximate nearest neighbor search.</title>
<author><name sortKey="Wang, Jingdong" sort="Wang, Jingdong" uniqKey="Wang J" first="Jingdong" last="Wang">Jingdong Wang</name>
<affiliation wicri:level="3"><nlm:affiliation>Microsoft Research Aisa, Beijing.</nlm:affiliation>
<country>République populaire de Chine</country>
<placeName><settlement type="city">Pékin</settlement>
</placeName>
<wicri:orgArea>Microsoft Research Aisa</wicri:orgArea>
</affiliation>
</author>
<author><name sortKey="Wang, Naiyan" sort="Wang, Naiyan" uniqKey="Wang N" first="Naiyan" last="Wang">Naiyan Wang</name>
<affiliation wicri:level="1"><nlm:affiliation>The Hong Kong University of Science and Technology, Hong Kong.</nlm:affiliation>
<country xml:lang="fr">Hong Kong</country>
<wicri:regionArea>The Hong Kong University of Science and Technology</wicri:regionArea>
</affiliation>
</author>
<author><name sortKey="Jia, You" sort="Jia, You" uniqKey="Jia Y" first="You" last="Jia">You Jia</name>
<affiliation wicri:level="3"><nlm:affiliation>Carnegie Mellon University, Pittsburgh.</nlm:affiliation>
<country>États-Unis</country>
<placeName><settlement type="city">Pittsburgh</settlement>
<region type="state">Pennsylvanie</region>
</placeName>
<wicri:orgArea>Carnegie Mellon University</wicri:orgArea>
</affiliation>
</author>
<author><name sortKey="Li, Jian" sort="Li, Jian" uniqKey="Li J" first="Jian" last="Li">Jian Li</name>
<affiliation wicri:level="3"><nlm:affiliation>Tsinghua University, Beijing.</nlm:affiliation>
<country>République populaire de Chine</country>
<placeName><settlement type="city">Pékin</settlement>
</placeName>
<wicri:orgArea>Tsinghua University</wicri:orgArea>
</affiliation>
</author>
<author><name sortKey="Zeng, Gang" sort="Zeng, Gang" uniqKey="Zeng G" first="Gang" last="Zeng">Gang Zeng</name>
<affiliation wicri:level="3"><nlm:affiliation>Peking University, Beijing.</nlm:affiliation>
<country>République populaire de Chine</country>
<placeName><settlement type="city">Pékin</settlement>
</placeName>
<wicri:orgArea>Peking University</wicri:orgArea>
</affiliation>
</author>
<author><name sortKey="Zha, Hongbin" sort="Zha, Hongbin" uniqKey="Zha H" first="Hongbin" last="Zha">Hongbin Zha</name>
<affiliation wicri:level="3"><nlm:affiliation>Peking University, Beijing.</nlm:affiliation>
<country>République populaire de Chine</country>
<placeName><settlement type="city">Pékin</settlement>
</placeName>
<wicri:orgArea>Peking University</wicri:orgArea>
</affiliation>
</author>
<author><name sortKey="Hua, Xian Sheng" sort="Hua, Xian Sheng" uniqKey="Hua X" first="Xian-Sheng" last="Hua">Xian-Sheng Hua</name>
<affiliation><nlm:affiliation>Microsoft Corporation, Bellevue.</nlm:affiliation>
<wicri:noCountry code="subField">Bellevue</wicri:noCountry>
</affiliation>
</author>
</analytic>
<series><title level="j">IEEE transactions on pattern analysis and machine intelligence</title>
<idno type="eISSN">1939-3539</idno>
<imprint><date when="2014" type="published">2014</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term>
<term>Artificial Intelligence</term>
<term>Image Enhancement (methods)</term>
<term>Image Interpretation, Computer-Assisted (methods)</term>
<term>Pattern Recognition, Automated (methods)</term>
<term>Reproducibility of Results</term>
<term>Sensitivity and Specificity</term>
<term>Subtraction Technique</term>
</keywords>
<keywords scheme="KwdFr" xml:lang="fr"><term>Algorithmes</term>
<term>Amélioration d'image ()</term>
<term>Intelligence artificielle</term>
<term>Interprétation d'image assistée par ordinateur ()</term>
<term>Reconnaissance automatique des formes ()</term>
<term>Reproductibilité des résultats</term>
<term>Sensibilité et spécificité</term>
<term>Technique de soustraction</term>
</keywords>
<keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Image Enhancement</term>
<term>Image Interpretation, Computer-Assisted</term>
<term>Pattern Recognition, Automated</term>
</keywords>
<keywords scheme="MESH" xml:lang="en"><term>Algorithms</term>
<term>Artificial Intelligence</term>
<term>Reproducibility of Results</term>
<term>Sensitivity and Specificity</term>
<term>Subtraction Technique</term>
</keywords>
<keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term>
<term>Amélioration d'image</term>
<term>Intelligence artificielle</term>
<term>Interprétation d'image assistée par ordinateur</term>
<term>Reconnaissance automatique des formes</term>
<term>Reproductibilité des résultats</term>
<term>Sensibilité et spécificité</term>
<term>Technique de soustraction</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We address the problem of approximate nearest neighbor (ANN) search for visual descriptor indexing. Most spatial partition trees, such as KD trees, VP trees, and so on, follow the hierarchical binary space partitioning framework. The key effort is to design different partition functions (hyperplane or hypersphere) to divide the points so that 1) the data points can be well grouped to support effective NN candidate location and 2) the partition functions can be quickly evaluated to support efficient NN candidate location. We design a trinary-projection direction-based partition function. The trinary-projection direction is defined as a combination of a few coordinate axes with the weights being 1 or -1. We pursue the projection direction using the widely adopted maximum variance criterion to guarantee good space partitioning and find fewer coordinate axes to guarantee efficient partition function evaluation. We present a coordinate-wise enumeration algorithm to find the principal trinary-projection direction. In addition, we provide an extension using multiple randomized trees for improved performance. We justify our approach on large-scale local patch indexing and similar image search.</div>
</front>
</TEI>
<affiliations><list><country><li>Hong Kong</li>
<li>République populaire de Chine</li>
<li>États-Unis</li>
</country>
<region><li>Pennsylvanie</li>
</region>
<settlement><li>Pittsburgh</li>
<li>Pékin</li>
</settlement>
</list>
<tree><noCountry><name sortKey="Hua, Xian Sheng" sort="Hua, Xian Sheng" uniqKey="Hua X" first="Xian-Sheng" last="Hua">Xian-Sheng Hua</name>
</noCountry>
<country name="République populaire de Chine"><noRegion><name sortKey="Wang, Jingdong" sort="Wang, Jingdong" uniqKey="Wang J" first="Jingdong" last="Wang">Jingdong Wang</name>
</noRegion>
<name sortKey="Li, Jian" sort="Li, Jian" uniqKey="Li J" first="Jian" last="Li">Jian Li</name>
<name sortKey="Zeng, Gang" sort="Zeng, Gang" uniqKey="Zeng G" first="Gang" last="Zeng">Gang Zeng</name>
<name sortKey="Zha, Hongbin" sort="Zha, Hongbin" uniqKey="Zha H" first="Hongbin" last="Zha">Hongbin Zha</name>
</country>
<country name="Hong Kong"><noRegion><name sortKey="Wang, Naiyan" sort="Wang, Naiyan" uniqKey="Wang N" first="Naiyan" last="Wang">Naiyan Wang</name>
</noRegion>
</country>
<country name="États-Unis"><region name="Pennsylvanie"><name sortKey="Jia, You" sort="Jia, You" uniqKey="Jia Y" first="You" last="Jia">You Jia</name>
</region>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000A70 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000A70 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Amérique
   |area=    PittsburghV1
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     pubmed:24356357
   |texte=   Trinary-projection trees for approximate nearest neighbor search.
}}

Pour générer des pages wiki

HfdIndexSelect -h $EXPLOR_AREA/Data/Main/Exploration/RBID.i   -Sk "pubmed:24356357" \
       | HfdSelect -Kh $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd   \
       | NlmPubMed2Wicri -a PittsburghV1

This area was generated with Dilib version V0.6.38.
Data generation: Fri Jun 18 17:37:45 2021. Site generation: Fri Jun 18 18:15:47 2021

Serveur d'exploration sur Pittsburgh

Trinary-projection trees for approximate nearest neighbor search.

Trinary-projection trees for approximate nearest neighbor search.

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

Pour générer des pages wiki

	Serveur d'exploration sur Pittsburgh
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.